
/*
 * Question: Suppose that a triple (F, C, L/R) represents
 * an edge of a binary tree.
 *      F: parent
 *      C: child
 *      L/R: C is F's left child or right child
 * All triples' C are in level order.
 * F = '^', C is the root.
 * C = '^', input is terminal.
 * For example:
 *      ^AL
 *      ABL
 *      ACR
 *      BDL
 *      CEL
 *      CFR
 *      DGR
 *      FHL
 *      ^^L
 */

#include <iostream>
#include <queue>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

void create(bitree *&rt, const char *filename)
{
    char n[4];
    bitree *p, *f;
    queue<bitree *> q;
	ifstream input(filename);

    f = NULL;
    input >> n;
    while(n[0]!='^' || n[1]!='^'){
        p = new bitree;
        p->key = n[1];
        p->lchild = p->rchild = NULL;
        if(n[0] != '^'){
            while(!f || f->key != n[0]){
                f = q.front();
                q.pop();
            }
            if (n[2] == 'L') f->lchild = p;
            else f->rchild = p;
        }
        else rt = p;
        q.push(p);
        input >> n;
    }
	input.close();

    return;
}

int main()
{
    bitree *rt;

    create(rt, "ex50.txt");
    bitree_print(rt);
    bitree_destory(rt);

    return 0;
}
